Szyfr

To zadanie pojawiło się równolegle na finale IX OI. Polecamy wysyłać rozwiązania do tamtego zadania, to zostanie wkrótce usunięte z serwisu.

Dany jest ciąg dodatnich liczb całkowitych (dla ). Ciąg ten jest używany do szyfrowania -bitowych wiadomości. Jeśli mamy wiadomość, której kolejne bity tworzą ciąg (), to po zaszyfrowaniu ma ona postać liczby:

Zadanie

Masz dane zaszyfrowane wiadomości oraz ciągi liczb , których użyto do ich zaszyfrowania. Twoje zadanie polega na odkodowaniu zaszyfrowanych wiadomości i napisaniu programu, który na podstawie numeru wiadomości wypisuje odkodowaną wiadomość.

To zadanie ma szczególną postać. Masz do dyspozycji wszystkie dane wejściowe: szy_in.zip.

Dane wejściowe

Dysponujesz dziesięcioma zestawami danych. Każdy zestaw jest zapisany w osobnym pliku: szyk.in, gdzie k jest numerem zestawu. W pierwszym wierszu każdego z tych plików znajduje się jedna liczba całkowita , . W kolejnych wierszach zapisany jest ciąg liczb : w -ym wierszu zapisana jest jedna dodatnia liczba całkowita . Suma liczb nie przekracza . W -im wierszu zapisana jest jedna liczba całkowita -- zaszyfrowana wiadomość, .

Wejście

W pierwszym wierszu wejścia dla programu jest zapisany numer zestawu danych wejściowych , . W kolejnych liniach wejścia zapisany jest zestaw danych numer .

Wyjście

W pierwszym wierszu wyjścia należy zapisać odszyfrowaną wiadomość z pliku szyk.in, tzn. kolejne liczby , bez żadnych odstępów między nimi. Dane testowe zostały dobrane tak, że zaszyfrowane wiadomości są określone jednoznacznie.

Przykład

Dla danych wejściowych:

0
24
19226985
123697
67356296
19721773
1113273
69335448
23680077
9029881
85168664
93676782
5253843
77616588
78572630
13375812
17199980
101508862
59248276
3505733
35790095
62028546
85726819
56462819
103373994
91757169
667509506

poprawną odpowiedzią jest:

110001000101101100010101